Limited carry-in technique for real-time multi-core scheduling

Schedulability analysis has been widely studied to provide offline timing guarantees for a set of real-time tasks. The so-called limited carry-in technique, which can be orthogonally incorporated into many different multi-core schedulability analysis methods, was originally introduced for Earliest Deadline First (EDF) scheduling to derive a tighter bound on the amount of interference of carry-in jobs at the expense of investigating a pseudo-polynomial number of intervals. This technique has been later adapted for Fixed-Priority (FP) scheduling to obtain the carry-in bound efficiently by examining only one interval, leading to a significant improvement in multi-core schedulability analysis. However, such a successful result has not yet been transferred to any other non-FP scheduling algorithms. Motivated by this, this paper presents a generic limited carry-in technique that is applicable to any work-conserving algorithms. Specifically, this paper derives a carry-in bound in an algorithm-independent manner and demonstrates how to apply the bound to existing non-FP schedulability analysis methods for better schedulability.     

Regular corecursion in Prolog

Corecursion is the ability of defining a function that produces some infinite data in terms of the function and the data itself, as supported by lazy evaluation. However, in languages such as Haskell strict operations fail to terminate even on infinite regular data, that is, cyclic data.Regular corecursion is naturally supported by coinductive Prolog, an extension where predicates can be interpreted either inductively or coinductively, that has proved to be useful for formal verification, static analysis and symbolic evaluation of programs.In this paper we use the meta-programming facilities offered by Prolog to propose extensions to coinductive Prolog aiming to make regular corecursion more expressive and easier to program with.First, we propose a new interpreter to solve the problem of non-terminating failure as experienced with the standard semantics of coinduction (as supported, for instance, in SWI-Prolog). Another problem with the standard semantics is that predicates expressed in terms of existential quantification over a regular term cannot directly defined by coinduction; to this aim, we introduce finally clauses, to allow more flexibility in coinductive definitions.Then we investigate the possibility of annotating arguments of coinductive predicates, to restrict coinductive definitions to a subset of the arguments; this allows more efficient definitions, and further enhance the expressive power of coinductive Prolog.We investigate the effectiveness of such features by showing different example programs manipulating several kinds of cyclic values, ranging from automata and context free grammars to graphs and repeating decimals; the examples show how computations on cyclic values can be expressed with concise and relatively simple programs.The semantics defined by these vanilla meta-interpreters are an interesting starting point for a more mature design and implementation of coinductive Prolog.     

Interaction design for supporting communication between Chinese sojourners

In our global village, distance is not a barrier anymore for traveling. People experience new cultures and face accompanying difficulties in order to live anywhere. Social support can help these sojourners to cope with difficulties, such as culture shock. In this paper, we investigate how computer-mediated communication (CMC) tools can facilitate social support when living physically separated from loved-ones in different cultures. The goal is to understand the design considerations necessary to design new CMC tools. We studied communication practices of Chinese sojourners living in the Netherlands and the use of a technology probe with a novel video communication system. These results led to recommendations which can help designers to design interactive communication tools that facilitate communication across cultures. We conclude the paper with an interactive communication device called Circadian, which was designed based on these recommendations. We experienced the design recommendations to be abstract enough to leave space for creativity while providing a set of clear requirements which we used to base design decisions upon.     

Stochastic facility location with general long-run costs and convex short-run costs

This paper addresses the problem of minimizing the expected cost of locating a number of single product facilities and allocating uncertain customer demand to these facilities. The total costs consist of two components: firstly linear transportation cost and secondly the costs of investing in a facility as well as maintaining and operating it. These facility costs are general and non-linear in shape and could express both changing economies of scale and diseconomies of scale. We formulate the problem as a two-stage stochastic programming model where both demand and short-run costs may be uncertain at the investment time. We use a solution method based on Lagrangean relaxation, and show computational results for a slaughterhouse location case from the Norwegian meat industry.     

A survey on the history of transaction management: from flat to grid transactions

Transactions have been around since the Seventies to provide reliable information processing in automated information systems. Originally developed for simple ‘debit-credit’ style database operations in centralized systems, they have moved into much more complex application domains including aspects like distribution, process-orientation and loose coupling. The amount of published research work on transactions is huge and a number of overview papers and books already exist. A concise historic analysis providing an overview of the various phases of development of transaction models and mechanisms in the context of growing complexity of application domains is still missing, however. To fill this gap, this paper presents a historic overview of transaction models organized in several ‘transaction management eras’, thereby investigating numerous transaction models ranging from the classical flat transactions, via advanced and workflow transactions to the Web Services and Grid transaction models. The key concepts and techniques with respect to transaction management are investigated. Placing well-known research efforts in historical perspective reveals specific trends and developments in the area of transaction management. As such, this paper provides a comprehensive, structured overview of developments in the area.     

A class-based scheme for E-commerce web servers: Formal specification and performance evaluation

This paper is an investigation into the performance of E-commerce applications. E-commerce has become one of the most popular applications of the web as a large population of web users is now benefiting from various on-line services including product searches, product purchases and product comparison. E-commerce provides users with 24-7 shopping facilities. However, the consequence of these benefits and facilities is the excessive load on E-commerce web servers and the performance degradation of E-commerce (eCom) requests they process. This paper addresses this issue and proposes a class-based priority scheme which classifies eCom requests into high and low priority requests. In E-commerce, some requests (e.g. payment) are generally considered more important than others (e.g. search or browse). We believe that by assigning class-based priorities at multiple service levels, E-commerce web servers can perform better and can improve the performance of high priority eCom requests. In this paper, we formally specify and implement the proposed scheme and evaluate its performance using multiple servers. Experimental results demonstrate that the proposed scheme significantly improves the performance of high priority eCom requests.     

Extreme simplification and rendering of point sets using algebraic multigrid

We present a novel approach for extreme simplification of point set models, in the context of real-time rendering. Point sets are often rendered using simple point primitives, such as oriented discs. However, this requires using many primitives to render even moderately simple shapes. Often, one wishes to render a simplified model using only a few primitives, thus trading accuracy for simplicity. For this goal, we propose a more complex primitive, called a splat, that is able to approximate larger and more complex surface areas than oriented discs. We construct our primitive by decomposing the model into quasi-flat regions, using an efficient algebraic multigrid algorithm. Next, we encode these regions into splats implemented as planar support polygons textured with color and transparency information and render the splats using a special blending algorithm. Our approach combines the advantages of mesh-less point-based techniques with traditional polygon-based techniques. We demonstrate our method on various models.     

An investigation of the option space in conceptual building design for advanced building simulation

This article describes research conducted to gather empirical evidence on size, character and content of the option space in building design projects. This option space is the key starting point for the work of any climate engineer using building performance simulation who is supporting the design process. The underlying goal is to strengthen the role of advanced computing in building design, especially in the early conceptual stage, through a better integration of building performance simulation tools augmented with uncertainty analysis and sensitivity analysis. Better integration will need to assist design rather than automate design, allowing a spontaneous, creative and flexible process that acknowledges the expertise of the design team members. This research investigates and contrasts emergent option spaces and their inherent uncertainties in an artificial setting (student design studios) and in real-life scenarios (commercial design project case studies). The findings provide empirical evidence of the high variability of the option space that can be subjected to uncertainty analysis and sensitivity analysis.     

Online hybrid traffic classifier for Peer-to-Peer systems based on network processors

It is estimated that 70% or more of broadband bandwidth is consumed by transmitting music, games, video and other content through Peer-to-Peer (P2P) clients. In order to detect, identify, and manage P2P traffic, some port, payload and transport layer feature based methods were proposed. Most of them were applied to offline traffic classification mainly due to the performance reason. In this paper, a network processors (NPs) based online hybrid traffic classifier is proposed. The designed hardware classifier is able to classify P2P traffic based on the static characteristic namely on line speed, and the Flexible Neural Tree(FNT) based software classifier helps learning and selecting P2P traffic attributes from the statistical characteristics of the P2P traffic. Experiment results illustrate that the hybrid classifier performs well for online classification of P2P traffic from gigabit network. The proposed framework also depicts good expansion capabilities to add new P2P features and to adapt to new P2P applications online.